package easy._107_BinaryTreeLevelOrderTraversalII;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinaryTreeLevelOrderTraversalII {
    //速度过慢
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelList = new ArrayList<List<Integer>>();
        List<TreeNode> tempList = new ArrayList<TreeNode>();
        if(root==null) return levelList;
        tempList.add(root);
        while(!tempList.isEmpty()){
            List<Integer> tempNumList = new ArrayList<Integer>();
            List<TreeNode> tempNodeList = new ArrayList<TreeNode>();
            for(TreeNode node:tempList){
                tempNumList.add(node.val);
                TreeNode leftNode = node.left;
                TreeNode rightNode = node.right;
                if(leftNode!=null){
                    tempNodeList.add(leftNode);
                }
                if(rightNode!=null){
                    tempNodeList.add(rightNode);
                }
            }
            tempList = tempNodeList;
            levelList.add(tempNumList);
        }
        Collections.reverse(levelList);
        System.out.println(levelList);
        return levelList;
    }
}
